Integer Programming
Integer programming expresses the optimization of a linear function subject to a set of linear constraints over integer variables.
The statements presented in Linear programming: a production planning example are all linear programming models. However, linear programs with very large numbers of variables and constraints can be solved efficiently. Unfortunately, this is no longer true when the variables are required to take integer values. Integer programming is the class of problems that can be expressed as the optimization of a linear function subject to a set of linear constraints over integer variables. It is in fact NP-hard. More important, perhaps, is the fact that the integer programs that can be solved to provable optimality in reasonable time are much smaller in size than their linear programming counterparts. There are exceptions, of course, and this documentation describes several important classes of integer programs that can be solved efficiently, but users of OPL should be warned that discrete problems are in general much harder to solve than linear programs.
Integer programming algorithms minimize or maximize a function subject to equality, inequality, and integer constraints. Integer constraints restrict some or all of the variables in the optimization problem to take on only integer values. This enables accurate modeling of problems involving discrete quantities (such as shares of a stock) or yes-or-no decisions. When there are integer constraints on only some of the variables, the problem is called a mixed-integer program (MIP). Example integer programming problems include portfolio optimization in finance, optimal dispatch of generating units (unit commitment) in energy production, design optimization in engineering, and scheduling and routing in transportation and supply chain applications.
Integer programming is the mathematical problem of finding a vector x that minimizes the function:
This section introduces three classical approaches for solving integer programs, namely, branch-and-bound, cutting plane, and Benders decomposition. Although all approaches are capable of solving integer programs, their degrees of success vary in software implementation.
Branch-and-bound is a general-purpose approach capable of solving pure IP, mixed IP, and binary IP problems. For ease of exposition, sometimes we shall assume that the given problem is a pure IP problem because a similar algorithm can be applied to a mixed or binary IP problem. We also assume that the given problem is a maximization problem because modification of the algorithm for the minimization problem is straightforward.s
The method was first proposed by Ailsa Land and Alison Doig whilst carrying out research at the London School of Economics sponsored by British Petroleum in 1960 for discrete programming, and has become the most commonly used tool for solving NP-hard optimization problems. The name "branch and bound" first occurred in the work of Little et al. on the traveling salesman problem.[4][5] Branch and bound methods do not go deep like Depth-first search; the first direction is lateral movement in the tree similar to Breadth-first search (BFS).
To download GAMs file click here.
Dantzig-Wolfe decomposition as applied to an integer program is a specific form of problem reformulation that aims at providing a tighter linear programming relaxation bound. The reformulation gives rise to an integer master problem, whose typically large number of variables is dealt with implicitly by using an integer programming column generation procedure, also known as branch-and-price algorithm. There is a large class of integer programs that are well suited for this solution technique. In this paper, we propose to base the Dantzig-Wolfe decomposition of an integer program on the discretization of the integer polyhedron associated with a subsystem of constraints (as opposed to its convexification).
To download GAMs file click here.
In geometry, an equation in two variables is called a plane and an equation in n variables a hyperplane, strictly speaking. For simplicity, however, both in practice are often referred to as a plane, regardless of the number of variables. Strictly speaking, an inequality constraint in n variables is called a half-space, not a hyperplane. But an inequality constraint can always be converted to an equation by adding or subtracting a nonnegative slack variable. The term cutting plane is often used for an equality or inequality constraint that can cut off a fractional part of an LP feasible region, without excluding any integer feasible solution. In the cutting plane approach, one or more such cutting planes are added to the current LP simplex tableau, which in turn are resolved for a new LP optimum. This process is repeated until the prescribed integer requirements are satisfied. In this text, the collection of all such cutting plane methods will be called a cutting plane approach (more specifically, a dual cutting plane approach, due to the use of the dual simplex method for LP reoptimization).
Cutting planes were proposed by Ralph Gomory in the 1950s as a method for solving integer programming and mixed-integer programming problems. However, most experts, including Gomory himself, considered them to be impractical due to numerical instability, as well as ineffective because many rounds of cuts were needed to make progress towards the solution. Things turned around when in the mid-1990s Gérard Cornuéjols and co-workers showed them to be very effective in combination with branch-and-bound (called branch-and-cut) and ways to overcome numerical instabilities. Nowadays, all commercial MILP solvers use Gomory cuts in one way or another. Gomory cuts are very efficiently generated from a simplex tableau, whereas many other types of cuts are either expensive or even NP-hard to separate. Among other general cuts for MILP, most notably lift-and-project dominates Gomory cuts.
A large variety of cutting plane methods were developed during the 1950s and 1960s. Among them, the most prominent ones belong to the class of dual cutting plane approach such as the fractional and mixed cutting plane methods developed by Gomory. This class shares a common solution algorithm when they are utilized as a stand-alone solver.
* Step 1: Solve the integer program as if it were a linear program. If it is infeasible, so is the integer program and then stop. Else if an LP optimal solution satisfying the integer requirements is found, then the IP is solved. Otherwise, go to step 2.
* Step 2: Select a row to be a generating row (or source row) from the LP optimum simplex tableau.
* Step 3:Derive a cut constraint from the generating row and augment it to the current tableau, resulting in a primal infeasible solution.
* Step 4: Apply the dual simplex method to reoptimize the augmented linear program. If the new LP optimum satisfies the integer requirements, the original MIP program is solved. Otherwise, go to step 2.
Benders decomposition (or Benders' decomposition) is a technique in mathematical programming that allows the solution of very large linear programming problems that have a special block structure. This block structure often occurs in applications such as stochastic programming as the uncertainty is usually represented with scenarios. The technique is named after Jacques F. Benders.
The strategy behind Benders decomposition can be summarized as divide-and-conquer. That is, in Benders decomposition, the variables of the original problem are divided into two subsets so that a first-stage master problem is solved over the first set of variables, and the values for the second set of variables are determined in a second-stage subproblem for a given first-stage solution. If the subproblem determines that the fixed first-stage decisions are in fact infeasible, then so-called Benders cuts are generated and added to the master problem, which is then re-solved until no cuts can be generated. Since Benders decomposition adds new constraints as it progresses towards a solution, the approach is called "row generation".
To download GAMs file click here.